package com.lfg.leetcode.leetcode300;

public class No321maxNumber {
    public static void main(String[] args) {
        int[] ret = maxNumber(new int[]{2, 0, 0, 2}, new int[]{2, 0, 2}, 7);
        for (int i : ret) {
            System.out.println("[" + i + "]");
        }

    }


    public static int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] ret = new int[k];
        if (k == 0) {
            return ret;
        }
        int start = Math.max(0, k - nums2.length);

        for (int length1 = start; length1 <= k && length1 <= nums1.length; length1++) {
            int[] result1 = findMaxNumber(nums1, length1);
            int[] result2 = findMaxNumber(nums2, k - length1);
            int[] array = merge(result1, result2);
            if (compare(array, 0, ret, 0)) {
                ret = array;
            }
        }
        return ret;
    }

    private static boolean compare(int[] nums1, int i, int[] nums2, int j) {
        while (i < nums1.length && j < nums2.length) {
            int a = nums1[i++];
            int b = nums2[j++];
            if (b < a) {
                return true;
            } else if (a < b) {
                return false;
            }
        }
        if (i < nums1.length) {
            return true;
        }
        return false;
    }

    private static int[] merge(int[] nums1, int[] nums2) {
        int[] ret = new int[nums1.length + nums2.length];
        int i = 0, j = 0;
        int index = 0;
        while (index < ret.length) {
            if (compare(nums1, i, nums2, j)) {
                ret[index++] = nums1[i++];
            } else {
                ret[index++] = nums2[j++];
            }
        }
        return ret;
    }

    private static int[] findMaxNumber(int[] nums, int length) {
        int[] ret = new int[length];
        if (length == 0) {
            return ret;
        }
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            while (index > 0 && nums.length - i > length - index && ret[index - 1] < nums[i]) {
                index--;
            }
            if (index < length) {
                ret[index++] = nums[i];
            }
        }
        return ret;
    }


}
